package com.yangzhe.algorithm.c037;

// 修剪搜索二叉树
// 测试链接 : https://leetcode.cn/problems/trim-a-binary-search-tree/
public class Code06_MyTrimBinarySearchTree {

    // 不提交这个类
    public static class TreeNode {
        public int val;
        public TreeNode left;
        public TreeNode right;
    }

    /**
     * 搜索二叉树：左边所有节点都比当前节点小，右边所有节点都比当前节点大
     * <p>
     * 思路：递归修剪
     * 1. 当前节点比low小，则当前节点及其左子树都修剪掉，返回修剪右子树的结果
     * 2. 当前节点比high大，则当前节点及其右子树都修剪掉，返回修建左子树的结果
     * 3. 当前节点符合low和high的区间，则修剪左、右子树并连接起来
     * 4. 修建后根节点可能会变化
     *
     * @param root
     * @param low
     * @param high
     * @return
     */
    public TreeNode trimBST(TreeNode root, int low, int high) {
        if (root == null) {
            return null;
        }

        // 1. 当前节点比low小，则当前节点及其左子树都修剪掉，返回修剪右子树的结果
        if (root.val < low) {
            return trimBST(root.right, low, high);
        }
        // 2. 当前节点比high大，则当前节点及其右子树都修剪掉，返回修建左子树的结果
        else if (root.val > high) {
            return trimBST(root.left, low, high);
        } else {
            root.left = trimBST(root.left, low, high);
            root.right = trimBST(root.right, low, high);

            return root;
        }
    }
}
